Reverse nodes in K-group

Time: O(N); Space: O(1); hard

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example 1:

Input: head = {ListNode} 1->2->3->4->5->None, k = 2

Output: {ListNode} 2->1->4->3->5->None

Example 2:

Input: head = {ListNode} 1->2->3->4->5->None, k = 3

Output: {ListNode} 3->2->1->4->5->None

Notes:

  • Only constant extra memory is allowed.

  • You may not alter the values in the list’s nodes, only nodes itself may be changed.

[2]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def reverseKGroup(self, head, k):
        """
        type head: ListNode
        type k: int
        rtype: ListNode
        """
        dummy = ListNode(-1)
        dummy.next = head

        cur, cur_dummy = head, dummy
        length = 0

        while cur:
            next_cur = cur.next
            length = (length + 1) % k

            if length == 0:
                next_dummy = cur_dummy.next
                self.reverse(cur_dummy, cur.next)
                cur_dummy = next_dummy

            cur = next_cur

        return dummy.next

    def reverse(self, begin, end):
            first = begin.next
            cur = first.next

            while cur != end:
                first.next = cur.next
                cur.next = begin.next
                begin.next = cur
                cur = first.next

[4]:

s = Solution1()

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k = 2
res = s.reverseKGroup(head, k)

exp = [2,1,4,3,5]
for val in exp:
    assert res.val == val
    res = res.next